Method: negamax(IKopplung, State, Integer, Integer, Integer)

1: package de.fhdw.gaming.ipspiel23.gst.strategies.impl;
2:
3: import java.util.Collection;
4: import java.util.Optional;
5:
6: import de.fhdw.gaming.core.domain.GameException;
7: import de.fhdw.gaming.core.domain.Move;
8: import de.fhdw.gaming.core.domain.Player;
9: import de.fhdw.gaming.core.domain.State;
10: import de.fhdw.gaming.ipspiel23.gst.domain.IKopplung;
11: import de.fhdw.gaming.ipspiel23.gst.strategies.domain.IGstKopplungsMiniMaxStrategy;
12:
13: /**
14: * An implementation of the IGstKopplungsMiniMaxStrategy interface using the
15: * NegaMax algorithm with alpha beta pruning and Time based Iterative Deepening.
16: *
17: * @param <P> The type of player in the game.
18: * @param <S> The type of state in the game.
19: * @author borkowitz
20: */
21: public class GstKopplungNegaMax<P extends Player<P>, S extends State<P, S>>
22: implements IGstKopplungsMiniMaxStrategy<P, S> {
23:
24: /**
25: * Calculates the best move for the current player of a Game in a given Game state using the NegaMax algorithm.
26: * Too complex, but not easily simplifyable. Warning suppressed.
27: *
28: * @param kopplung The game object representing the specific game being played.
29: * @param state The current state of the game.
30: * @param maximumComputationTime The maximum computation time allowed for calculating the move.
31: * @return An optional containing the calculated best move, or empty if no move is available.
32: */
33: @SuppressWarnings({ "checkstyle:CyclomaticComplexity", "PMD.CyclomaticComplexity", "PMD.CognitiveComplexity" })
34: @Override
35: public Optional<Move<P, S>> calculateBestMove(final IKopplung<P, S> kopplung, final S state, // NOPMD by Dave on
36: // 26.06.23, 22:57
37: final int maximumComputationTime) {
38: Optional<Move<P, S>> bestMove = Optional.empty();
39: try {
40: final Optional<Collection<Move<P, S>>> possiblesMovesOptional = kopplung.getPossibleMoves(state);
41: if (possiblesMovesOptional.isPresent() && possiblesMovesOptional.get().size() > 0) {
42: for (int i = 0; i < 10; i++) {
43: final Integer bestMoveScore = Integer.MIN_VALUE;
44: Optional<Move<P, S>> iterationBestMove = Optional.empty();
45: Integer iterationBestMoveScore = Integer.MIN_VALUE;
46: for (final Move<P, S> move : possiblesMovesOptional.get()) {
47: final S copiedState = state.deepCopy();
48: final P currentPlayer = kopplung.getCurrentPlayer(copiedState).get();
49: move.applyTo(copiedState, currentPlayer);
50: copiedState.nextTurn();
51: final Integer moveScore = -this.negamax(kopplung, copiedState, i, Integer.MIN_VALUE,
52: Integer.MAX_VALUE);
53: if (moveScore > iterationBestMoveScore) {
54: iterationBestMove = Optional.of(move);
55: iterationBestMoveScore = moveScore;
56: }
57: }
58: if (iterationBestMoveScore > bestMoveScore) {
59: bestMove = iterationBestMove;
60: }
61: }
62: }
63: return bestMove;
64: } catch (final Exception e) {
65: return bestMove;
66: }
67: }
68:
69: /**
70: * Extracted.
71: *
72: * @param kopplung
73: * @param state
74: * @param move
75: * @return
76: * @throws GameException
77: */
78: private S simulateMove(final IKopplung<P, S> kopplung, final S state, final Move<P, S> move) throws GameException {
79: final S copiedState = state.deepCopy();
80: final P currentPlayer = kopplung.getCurrentPlayer(copiedState).get();
81: move.applyTo(copiedState, currentPlayer);
82: copiedState.nextTurn();
83: return copiedState;
84: }
85:
86: /**
87: * Performs the NegaMax algorithm to evaluate the score of a Game state.
88: * Too complex, but not easily simplifyable. Warning suppressed.
89: *
90: * @param kopplung The game object representing the specific game being played.
91: * @param state The current state of the game.
92: * @param depth The current depth of the algorithm.
93: * @param alpha The alpha value for alpha-beta pruning.
94: * @param beta The beta value for alpha-beta pruning.
95: * @return The evaluated score of the state.
96: * @throws Exception
97: */
98: @SuppressWarnings({ "checkstyle:CyclomaticComplexity", "PMD.CyclomaticComplexity", "PMD.CognitiveComplexity" })
99:
100: private Integer negamax(final IKopplung<P, S> kopplung, final S state, final Integer depth, final Integer alpha,
101: final Integer beta) throws GameException {
102:• if (depth == 0 || kopplung.getIsGameOver(state).get()) {
103: return kopplung.evalState(state).get();
104: }
105: final Optional<Collection<Move<P, S>>> possiblesMovesOptional = kopplung.getPossibleMoves(state);
106:• if (possiblesMovesOptional.isPresent() && possiblesMovesOptional.get().size() > 0) {
107: Integer score = Integer.MIN_VALUE;
108: Integer modAlpha = alpha;
109:• for (final Move<P, S> move : possiblesMovesOptional.get()) {
110: final S copiedState = simulateMove(kopplung, state, move);
111: final Integer childScore = -this.negamax(kopplung, copiedState, depth - 1, -beta, -modAlpha);
112:• if (childScore > score) {
113: score = childScore + depth;
114: }
115: modAlpha = Math.max(modAlpha, score);
116:• if (modAlpha >= beta) {
117: break;
118: }
119: }
120: return score;
121: }
122: throw new GameException("Something went wrong with Negamax");
123: }
124: }